class Solution {
public:
    bool isNumber(char ch) {
        if (ch >= '0' && ch <= '9') return true;
        return false;
    }

    bool isLetter(char ch) {
        if (ch >= 'a' && ch <= 'z') return true;
        return false;
    }

    string getNum(string s, int& cur) {
        string ret = "";
        while (isNumber(s[cur])) {
            ret.push_back(s[cur++]);
        }
        return ret;
    }
    
    string decodeString(string s) {
        int cur = 0;
        stack<string> st;
        while (cur < s.size()) {
            if (isNumber(s[cur])) {
                string num = getNum(s, cur);
                st.push(num);
            } else if (isLetter(s[cur]) || s[cur] == '[') {
                st.push(string(1, s[cur++]));
            } else {
                cur++;
                string sub;
                while (st.top() != "[") {
                    sub = st.top() + sub;
                    st.pop();
                }
                st.pop();
                int count = atoi(st.top().c_str());
                st.pop();

                string sub_str;
                for (int i = 0; i < count; i++) {
                    sub_str += sub;
                }
                st.push(sub_str);
            }
        }
        string result;
        while (!st.empty()) {
            result = st.top() + result;
            st.pop();
        }
        return result;
    }
};
